ALGORITHMICS OF MATCHING UNDER PREFERENCES by MANLOVE DAVID

Author:MANLOVE DAVID [DAVID, MANLOVE]
Language: eng
Format: epub
Published: 2013-02-28T08:51:37+00:00

February 21, 2013

15:47

BC: 8591 - Algorithmics of matching - 2nd Reading

book

5.2. hr with lower and common quotas

237

What makes hr-cq hard is the existence of pairs of bounded sets of

hospitals that have a non-empty intersection, where neither bounded set

is contained in the other. In the absence of such bounded sets, efficient

algorithms and elegant structural results can be derived for this problem.

In a given hr-cq instance, define the set system of hospitals H to be nested3

if, for any bounded sets Hk, Hl ∈ H such that Hk ∩ Hl 6= ∅, either Hk ⊆ Hl

or Hl ⊆ Hk. Let hr-cq-nss denote the restriction of hr-cq in which the

set system of hospitals is nested.

Biró et al. [84] presented two algorithms for finding stable matchings

in a given instance of hr-cq-nss. These algorithms are resident-oriented

and hospital-oriented in that they find stable matchings that are resident-

optimal and hospital-optimal in precise senses, respectively.

As a by-

product of establishing the correctness of these algorithms, the authors

deduced that every instance of hr-cq-nss admits at least one stable match-

ing. The following theorems summarise the discussion in this paragraph,

indicating the complexity of the algorithms and the precise optimality prop-

erties that are satisfied in each case.

Theorem 5.6 ([84]).

Given an instance of hr-cq-nss, the resident-

oriented algorithm finds a stable matching M that is resident-optimal in the

following sense. In M , each assigned resident is assigned to the best hospital

that she could obtain in any stable matching, and each unassigned resident

is unassigned in every stable matching. The complexity of this algorithm

is O(km + pn1), where k is the maximum level of nesting (i.e., the maxi-

mum integer k such that there exist bounded sets Hi ⊂ H ⊂ · · · ⊂ H ),

1

i2

ik

m is the number of acceptable resident–hospital pairs, n1 is the number of

residents and p = |H| is the number of bounded sets.

Theorem 5.7 ([84]).

Given an instance of hr-cq-nss, the hospital-

oriented algorithm finds a stable matching M that is hospital-optimal in

the following sense. For any hospital hj ∈ H, there is no stable match-

ing in which hj is assigned a resident ri ∈ R\M(hj) whom hj prefers to

some member of M (hj). Also in M , each assigned resident is assigned to

the worst hospital that she could obtain in any stable matching, and each

unassigned resident is unassigned in any stable matching. The complexity

of this algorithm is O(n2m), where n2 is the number of hospitals and m is

the number of acceptable resident–hospital pairs.

3A nested set system is also referred to in the literature as a laminar family [290, 218].

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.